#include<bits/stdc++.h>
using namespace std;

//!! 找到(a<b<c)，b,c枚举使用双指针(一左一右向中间靠近)
//双指针可以将部分情况下的n^2变为n^1

// 思考题
// 既然三数之和可以使用双指针法，我们之前讲过的1.两数之和 (opens new window)，可不可以使用双指针法呢？

// 如果不能，题意如何更改就可以使用双指针法呢？ 大家留言说出自己的想法吧！

// 两数之和 就不能使用双指针法，因为1.两数之和 (opens new window)要求返回的是索引下标， 而双指针法一定要排序，一旦排序之后原数组的索引就被改变了。

// 如果1.两数之和 (opens new window)要求返回的是数值的话，就可以使用双指针法了

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int len = nums.size();
        for(int first=0; first<len; ++first){
            //与上一个答案不同(first)
            if(first > 0 && nums[first] == nums[first-1]) continue;
            int third = len - 1;
            for(int second=first+1; second<len; ++second){
                //与上一个答案不同(second16. 最接近的三数之和)
                if(second > first + 1 && nums[second] == nums[second-1]) continue;
                while(second < third && nums[second] + nums[third] > -nums[first]){
                    --third;
                }
                if(second == third) break;
                if(nums[second] + nums[third] + nums[first] == 0)
                    res.push_back({nums[first], nums[second], nums[third]});
            }
        }
        return res;
    }
};

int main(){
    
}